The invention disclosed herein relates generally to network configuration protocols. More specifically, the invention relates to providing redundancy and eliminating loops in disparate interconnected networks each implementing one or more independent instances of a layer 2 redundancy protocol or protocols.
Two basic requirements for computer networks are the availability of redundancy and the prevention of loops. Redundancy is needed so that a fault or break in a device or path in the network does not cut off traffic flow in the network. Loops occur when a network has multiple active paths between devices at any given time, resulting in the duplication of messages. Loops are prevented by keeping only one active path between devices at any given time. Since both redundancy and loop prevention involve configuration and selection of active and inactive paths, a network must carefully manage the states of its paths to satisfy both needs.
One solution to the problem of providing redundancy while preventing loops is the spanning tree algorithm or protocol. The spanning tree protocol, defined in IEEE 802.1, is used by bridges in a network to dynamically discover a subset of the network topology that provides path redundancy while preventing loops. Spanning tree protocol provides redundancy by defining a single tree that spans the bridges and maintaining all other paths and connections in a standby or blocked state. The protocol allows bridges to transmit messages to one another to thereby allow each bridge to select its place in the tree and which states should be applied to each of its ports to maintain that place. For example, a port in a given bridge that is connected to an active path at a given time is kept in a forwarding state in which all data traffic is received and transmitted to the next portion of the network; ports in the bridge that are connected to inactive paths are kept in a non-forwarding state, such as a blocking state, in which traffic is blocked through that port.
Bridges in a spanning tree network pass bridge protocol data units, or BPDUs, amongst themselves. Each BDPU comprises information including root, bridge and port identifiers, and path cost data. This information is used by the bridges, among other things, to “elect” one of the bridges in the spanning tree network to be a unique root bridge for the network, calculate the shortest least cost path from each bridge to the root bridge, select which ports will be blocking, and for each LAN, elect one of the bridges residing in the LAN to be a designated bridge.
In brief, the election of a root bridge is performed by each bridge initially assuming itself to be the root bridge, each bridge transmitting root BPDUs, each bridge comparing its BDPU information with that received from other bridges, and each bridge deciding whether to stop serving as a root and stop transmitting BPDUs when the configuration of another bridge as root is more advantageous than the bridge itself serving as root. Ports being converted from blocking to forwarding states and back again undergo several possible transition states depending upon the BPDUs received. Once the bridges have all reached their decisions, the network stabilizes or converges, thereby becoming loop-free. A similar process is followed after a link failure occurs in the network, in which case a new root and/or new active paths must be identified. An overview of the spanning tree protocol, which is well known to those of skill in the art, can be found in the document “Understanding Spanning-Tree Protocol”, located at http://www.cisco.com/univercd/cc/td/doc/product/rtrmgmt/sw_ntman/cwsimain/cwsi2/cwsiug2/v lan2/stpapp.htm and herein incorporated by reference in its entirety.
The spanning tree protocol, however, suffers from several limitations when implemented in multiple large interconnected networks. Standard spanning tree protocol is prone to slow convergence times, sometimes upward of 30 to 50 seconds, and does not scale well as a topology expands to include additional spanning tree nodes. Additionally, spanning tree domains must be continuous in order to ensure a loop free data path—changes within the spanning tree domain can affect all spanning tree members of that domain. Such ripple effects, for example, can cause problems in one city to affect other cites where large metroring topologies are implemented.
There is thus a need for systems and methods whereby networks are organized into layer 2 redundancy domains that overcome the drawbacks associated with current spanning tree protocol and other layer 2 redundancy protocol implementations and that are smaller, easier to manage, and faster converging. There is a further need for system and methods that allow an external network to host a plurality of customer networks, each implementing distinct instances of the spanning tree protocol, while maintaining the integrity of each of the hosted customer networks.